

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

#include "common/utils.hpp"

struct Node {
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}
    Node(int x) : val(x), left(nullptr), right(nullptr), next(nullptr) {}
    Node(int x, Node* l, Node* r, Node* n)
        : val(x), left(l), right(r), next(n) {}
};

// 填充每个节点的下一个右侧节点指针
// 双指针
Node* connect(Node* root) {
    std::queue<Node*> queue;

    if (root != nullptr) queue.push(root);

    while(!queue.empty()) {
        int size = queue.size();
        Node* preNode;
        Node* curNode;
        for (int i = 0; i < size; i++) {
            curNode = queue.front();
            queue.pop();
            if (i == 0) {
                preNode = curNode;
            } else {
                preNode->next = curNode;
                preNode = curNode;
            }

            if (curNode->left) queue.push(curNode->left);
            if (curNode->right) queue.push(curNode->right);
        }
        preNode->next = nullptr;
    }

    return root;
}

std::vector<std::string> traverseNode(Node* root) {
    std::vector<std::string> result;
    std::queue<Node*> queue;

    if (root != nullptr) queue.push(root);

    while(!queue.empty()) {
        Node* node = queue.front();
        queue.pop();
        std::string str = std::to_string(node->val);
        if (node->next == nullptr) {
            str += ("->#");
        } else {
            str += ("->" + std::to_string(node->next->val));
        }
        result.push_back(str);

        if (node->left) queue.push(node->left);
        if (node->right) queue.push(node->right);
    }

    return result;
}

Node* node = new Node(10, new Node(6, new Node(3), new Node(9), nullptr), new Node(16, new Node(14), new Node(19), nullptr), nullptr);

int main() {
    Node* root = connect(node);
    std::vector<std::string> res = traverseNode(root);
    for (int i = 0, size = res.size(); i < size; i++) {
        std::cout << res[i] << " ";
    }
    std::cout << "\n";
}